package com.order.www;

import java.util.HashMap;
import java.util.Map;

/**
 * Creared with IntelliJ IDEA.
 * Description:大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。
 * 斐波那契数列是一个满足 fib(x)=\left\{ \begin{array}{rcl} 1 & {x=1,2}\\ fib(x-1)+fib(x-2) &{x>2}\\ \end{array} \right.fib(x)={
 * 1
 * fib(x−1)+fib(x−2)
 * ​
 *
 * x=1,2
 * x>2
 * ​
 *   的数列
 * 数据范围：1\leq n\leq 401≤n≤40
 * User:yxd
 * Date:2022-02-01
 * Time:22:30
 */
public class Dp1 {
    public static void main(String[] args) {
        int n = 40;
        System.out.println(Fibonacci(n));
    }
    public static Map<Integer,Integer> map = new HashMap<>();
    public static int Fibonacci(int n) {
        /*动态规划
        if(n == 0)return n;
        int first = 1;
        int second = 1;
        int third = 1;
        while(n > 2){
            third = first + second;
            first = second;
            second = third;
            n --;
        }
        return third;*/
        /*递归
        if(n == 0)return 0;
        if(n <= 2)return 1;
        return Fibonacci(n - 1) + Fibonacci(n - 2);*/
        //hashmap
        if(n == 0)return 0;
        if(n <= 2)return 1;
        int prev = 0;
        if(map.containsKey(n - 2)){//有就直接获取
            prev = map.get(n - 2);
        }else{
            prev = Fibonacci(n - 2);//没有就创建再放入
            map.put(n - 2,prev);
        }
        int next = 0;
        if(map.containsKey(n - 1)){
            next = map.get(n - 1);
        }else{
            next = Fibonacci(n - 1);
            map.put(n - 1,next);
        }
        return prev + next;
    }
}
